##########################
###### MINI-MAX A-B ######
##########################
import time
import Config
# class AlphaBeta:
# # print utility value of root node (assuming it is max)
# # print names of all nodes visited during search
# def __init__(self, game_tree):
#     self.game_tree = game_tree  # GameTree
#     self.root = game_tree.root  # GameNode
#     return
BoardSituation = set()



def alpha_beta_search(node):

    global BoardSituation
    BoardSituation = set()

    infinity = float('inf')
    best_val = -infinity
    beta = infinity
    t = time.time()
    node.getSuccessors(BoardSituation)
    best_state = None
    for state in node.children:
        value = min_value(state, best_val, beta)
        if value > best_val:
            best_val = value
            best_state = state
    if best_state is None:
        print(11111111)

    if Config.DEBUG == True:
        print("AlphaBeta:  Utility Value of Root Node: = " + str(best_val))
        print("cost time is: " + str(time.time() - t))
        global count
        count = 1
        def countChild(node):
            global count
            count = count + len(node.children)
            for child in node.children:
                countChild(child)
        countChild(node)
        print("tree children is : " +str(count))
    return best_state.move

def max_value(node, alpha, beta):
    # print("AlphaBeta-->MAX: Visited Node")
    infinity = float('inf')
    value = -infinity

    node.getSuccessors(BoardSituation)
    if node.checkTerminal():
        return node.value
    for state in node.children:
        value = max(value, min_value(state, alpha, beta))
        if value >= beta:
            return value
        alpha = max(alpha, value)
    return value

def min_value(node, alpha, beta):
    # print("AlphaBeta-->MIN: Visited Node")

    infinity = float('inf')
    value = infinity
    node.getSuccessors(BoardSituation)

    #如果是终止节点 ，直接返回值
    if node.checkTerminal():
        return node.value
    for state in node.children:
        value = min(value,max_value(state, alpha, beta))
        if value <= alpha:
            return value
        beta = min(beta, value)

    return value
    #                     #
    #   UTILITY METHODS   #
    #                     #
    #
    # # successor states in a game tree are the child nodes...
    # def getSuccessors(self, node):
    #     assert node is not None
    #     return node.children
    #
    # # return true if the node has NO children (successor states)
    # # return false if the node has children (successor states)
    # def isTerminal(self, node):
    #     assert node is not None
    #     return len(node.children) == 0
    #
    # def getUtility(self, node):
    #     assert node is not None

